\documentclass{ctexart}

\usepackage{ctex}
\usepackage{tikz}
\usetikzlibrary{calc,positioning,shapes.geometric}
\usepackage{url}
\usepackage{graphicx}
\usepackage{float}
\usepackage{xcolor}
\usepackage{color}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{caption}
\usepackage{subfigure}
\usepackage{framed}
\usepackage{booktabs}
\usepackage{makecell}
\usepackage{geometry}
\usepackage{wrapfig}
\usepackage{abstract}
\usepackage{algorithmicx}
\usepackage[ruled]{algorithm}
\usepackage{algpseudocode}
\usepackage{setspace}
\usepackage{bm}
\usepackage{cite}
\usepackage{array}
\usepackage{textcomp}
\usepackage{listings}

\usepackage{geometry}
\geometry{right=2.5cm,left=2.5cm}

\newtheorem{theorem}{定理}

\pagenumbering{arabic}

\begin{document}
\begin{sloppypar}
\title{\vspace{-3cm} \textbf{Homework 1 of Numerical Analysis}}
\author{刘陈若\;$3200104872$\\信息与计算科学2001}
\date{}

\maketitle

\section*{Theoretical questions}
\subsection*{Problem \uppercase\expandafter{\romannumeral1}}
\begin{proof}[\textbf{Solution.}]
The width of the interval at $n$th step (Because the definition of 'at' is not clear enough, here we consider the interval as the one BEFORE $n$th bisection $e.g.$ When $n=1$, the width is $2$), denoted by $I_n$, is
\begin{equation}
    I_n=\frac{3.5-1.5}{2^{n-1}}=2^{2-n}
\end{equation}

Furthermore, the maximum possible distance between root $r$ and the midpoint of the interval (also refers to the interval BEFORE $n$th step) is $\frac{1}{2}I_n = 2^{1-n}$.
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral2}}
\begin{proof}[\textbf{Solution.}]
We first define $relative$ $error$ as the DISTANCE between root $r$ and one of the end point of the intervals where it is located DIVIDED BY $r$.

By definition, suppose $c_n$ is one of the interval end point of $r$ after $n$ steps, then we should have
\begin{equation}
    \frac{|r-c_n|}{r}\leq\epsilon \quad \Longleftarrow \quad \frac{b_0-a_0}{2^{n}a_0}\leq\epsilon
\end{equation}

In the transformation, we make use of $|r-c_n|\leq I_{n+1} = \left(b_0-a_0\right)/2^{n}$ and $a_0\leq r$. Separate variable $n$ to one side of the inequality, then we have
\begin{equation}
   n\geq \log_2 \frac{b_0-a_0}{\epsilon a_0}
\end{equation}
thus finishing the proof.
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral3}}
\begin{proof}[\textbf{Solution.}]
we use $p(x)=4x^3-2x^2+3$, $p'(x)=12x^2-4x$ and $Newton's$ $Method$
\begin{equation}
   x_{n+1} = x_{n} - \frac{p(x_n)}{p'(x_n)}, \quad x_0=-1
\end{equation}
for iteration. The results are shown in the table. Noted that infinite decimals is accurate to fifth decimal places.
\begin{table}[H]
\renewcommand{\arraystretch}{1.2}
 \centering
 \label{tab:pagenum}
 \setlength{\tabcolsep}{1cm}{

 \begin{tabular}{c c c c}
  \toprule
  \multicolumn{1}{c}{\textbf{$n$}}& \multicolumn{1}{c}{\textbf{$x_n$}}& \multicolumn{1}{c}{\textbf{$p(x_n)$}}& \multicolumn{1}{c}{\textbf{$p'(x_n)$}}\\
  \midrule

\multicolumn{1}{c}{$0$} & \multicolumn{1}{c}{$-1$}& \multicolumn{1}{c}{$-3$}& \multicolumn{1}{c}{$16$} \\
\multicolumn{1}{c}{$1$} & \multicolumn{1}{c}{$-0.8125$}& \multicolumn{1}{c}{$-0.46582$}& \multicolumn{1}{c}{$11.17188$} \\
\multicolumn{1}{c}{$2$} & \multicolumn{1}{c}{$-0.77080$}& \multicolumn{1}{c}{$-0.02014$}& \multicolumn{1}{c}{$10.21289$} \\
\multicolumn{1}{c}{$3$} & \multicolumn{1}{c}{$-0.76883$}& \multicolumn{1}{c}{$-0.00004$}& \multicolumn{1}{c}{$10.16859$} \\
\multicolumn{1}{c}{$4$} & \multicolumn{1}{c}{$-0.76883$}& \multicolumn{1}{c}{$-0.00000$}& \multicolumn{1}{c}{$10.16847$} \\
  \bottomrule
 \end{tabular}}
\end{table}
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral4}}
\begin{proof}[\textbf{Solution.}]
It should be noted that $C$ must depend on the root $r$. A strict proof has given to assistant Hu Shuang through Dingding, so here we only give a simple explanation.

Suppose $C$ only depend on $x_n$, $f$ and its finite order (otherwise the problem is meaningless) derivatives. Then considering $f(x)=e^x-1$ with root $r=0$, for the part of the function to the left of $x_n$ ($x_n>0)$, we can at least construct countable functions (using Taylor expansion of $f$ at $x=x_n$) which have the same value ($C$ depends) as $e^x-1$. Therefore, no matter what these functions on the left of $x_n$ look like, they have the same $C$ and $s$. However, obviously their roots are different, thus producing contradictions.

In fact, under the condition that $C$ also depends on the root $r$, $s$ can be any nonzero constant. Suppose $s=s_0$ ($s_0\neq0$), by iteration formula we have
\begin{equation}
   x_{n+1}-r = x_{n}-r - \frac{f(x_n)}{f'(x_0)}
\end{equation}
\begin{equation}
   \Longrightarrow \quad e_{n+1} = e^{s_0}_{n}\left[(x_{n}-r)^{1-s_0}-(x_{n}-r)^{-s_0}\frac{f(x_n)}{f'(x_0)}\right]
\end{equation}
Therefore, $s$ can be ANY nonzero constant $s_0$, and the corresponding $C$ is
\begin{equation}
   C=(x_{n}-r)^{1-s_0}-(x_{n}-r)^{-s_0}\frac{f(x_n)}{f'(x_0)}
\end{equation}
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral5}}
\begin{proof}[\textbf{Solution.}]
The iteration converges. For the initial value $x_0$, we discuss it in three cases.

If $x_0=0$, it's obvious that $x_n=0$ for any $n$ and the iteration is convergent.

If $0<x_0<\frac{\pi}{2}$, firstly we can conclude $x_n>0$ for any $n$ by an easy induction. Secondly, according to a common inequality $x<tanx$ ($x>0$), we have
\begin{equation}
   x_n=tanx_{n+1}>x_{n+1} \quad (n=1,2,\dots)
\end{equation}
Therefore, the sequence ${x_n}$ is monotonically decreasing with a lower bound $0$. Then it converges by \textbf{Theorem 1.12}.

If $0>x_0>-\frac{\pi}{2}$, similarly we know the sequence $\left\{x_n\right\}$ is monotonically increasing with a upper bound $0$. Then it converges by \textbf{Theorem 1.12}.
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral6}}
\begin{proof}[\textbf{Solution.}]
set $x_1=\frac{1}{p}$, $x_2=\frac{1}{p+\frac{1}{p}}$,$\dots$,and so forth. We first prove that the sequence $\left\{x_n\right\}$ converges.

As $p>1$, it's not difficult to have $x_n>0$ for any positive integer $n$. Then by the iteration $x_{n+1}=1/(x_n+p)$, we set $f(x)=1/(x+p)$ which satisfies
\begin{equation}
   |f(x)-f(y)|=\frac{|x-y|}{(p+x)(p+y)}<\frac{1}{p^2}|x-y|, \quad \forall x,y>0
\end{equation}
By \textbf{Definition 1.36} and \textbf{Theorem 1.38}, the sequence $\left\{x_n\right\}$ is convergent.

Now we can denote $x = lim_{x\rightarrow \infty}x_n$. Then by definition, $x$ satisfies the equation
\begin{equation}
   x=\frac{1}{p+x}, \quad x\geq 0
\end{equation}
Solve this equation we have the value of $x=\frac{-p+\sqrt{p^2+4}}{2}$.
\end{proof}

\subsection*{Problem \uppercase\expandafter{\romannumeral7}}
\begin{proof}[\textbf{Solution.}]
If $a_0<0<b_0$, then the inequality in Problem \uppercase\expandafter{\romannumeral2} is meaningless because $loga_0$ is undefined.

Additionally, using the previous symbols in Problem \uppercase\expandafter{\romannumeral1} and  \uppercase\expandafter{\romannumeral2}, we redefine $relative$ $error$ as the DISTANCE between root $r$ and one of the end point of the intervals where it is located DIVIDED BY $|r|$.
Then, after making use of $|r-c_n|\leq I_{n+1} = \left(b_0-a_0\right)/2^{n}$, similarly we have
\begin{equation}
    \frac{|r-c_n|}{|r|}\leq\epsilon \quad \Longleftarrow \quad n\geq \log_2 \frac{b_0-a_0}{\epsilon |r|}
\end{equation}

However, this inequality has to depend on $r$, because $|r|$ has no absolute relationship with $a_0$ and $b_0$. Besides, as $r\rightarrow0$, according to the inequality, $n\rightarrow \infty$, which is meaningless. Hence we conclude that the relative error is NOT a appropriate measure.
\end{proof}

\end{sloppypar}
\end{document}
